/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-08
 * Time: 12:47
 */
//插入排序算法，这是一种稳定的排序方法。
    //
public class InsertSort {
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void printArray(int[] arr) {
        for (int j : arr) {
            System.out.print( j + " " );
        }
        System.out.println();
    }
    //第一种方法
    private static void insertSort(int[] arr){
        //下标从0~0
        //0~1
        //0~2
        //0~3
        //0~n-1逐渐有序
        int n = arr.length;
        //从下标1开始排序
        for(int i=1;i<n;i++){
            //当前元素下标为i，与前面的元素逐一进行比较
            int j=i;
            while ( j>0 && arr[j-1]>arr[j] ){
                swap( arr, j, j-1);
                //让当前元素下标减一，直到找到自己应该在的位置
                j--;
            }
//            for(;j>0 && arr[j-1]>arr[j];j--){
//                swap( arr, j, j-1);
//            }
        }
    }
    public static void main (String[] args) {
        int[] arr={1,3,5,7,9,2,4,6,8,0};
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }
}
